Ee382c paper
__TOC__ Owners Paul, Ozen, Zheng, and Neeraj TO-DO * Review the paper guidelines guidelines * Continue to work up Introduction, Problem, Solution, and Critique sections (~6500 words = 10 pages. Currently 947/6500 words not counting the stuff that's going to get deleted) Topic Flow Control Buffer Allocation Introduction As technology scales in communication networks, buffer allocation becomes ever more critical. This paper explores various proposals for buffer allocation related to flow control. A brief description of the problem is provided, followed by some proposed solutions. The solutions are then analyzed to identify their strengths and weaknesses. Finally, a critique of the topic is provided. Channels are expensive resources and packet traversing between two points could block the channel due to lack of resources at receiver or intermediate points. This problem is unique to networks that use wormhole routing (i.e. attempt to save space). However this leads to unrelated traffic being also blocked causing lower throughput. This can be solved by adding virtual channels. Virtual channels decouple allocation of buffer space from channel bandwidth. This allows multiple stored packets to compete for bandwidth of single physical channel. If a packet is blocked then another packet could bypass it using the physical channel. The Problem Describe the problem: What problem are the papers you have chosen addressing? What are the constraints? How does one measure the quality of a solution? What makes this problem hard? What are the key issues? --Polkeem 05:37, 2 May 2007 (UTC) Fill in something here. I think the quality of the solution should be measured by the less number of buffers it takes to achieve similar throughput and latency as a different solution like virtual channel flow control. For flit-reservation Flow Control, this measure is well defined in the paper. This may not be the case for other papers. --Zhengli 04:25, 3 May 2007 (UTC)I suppose that we'd better describe the problem in formula: Given: Topology, Traffic Pattern, Routing algorithm(for simplicity, we can assume it is deterministic), Number of buffer space (Budget) Determine: for virtual channel flow control, how the buffer space should allocate to each router; how one router allocate its buffer quota to each input port; how each input port allocate its quota to each virtual channel Such that: The throughput of the whole network is Maximize Or, the average packet latency is Minimized Proposed Solutions Describe the solutions: What contribution does each of your papers make toward the solution of this problem? What are their strong points? What are their weak points? What remains to be done? Flit Reservation Flow Control 2 In flit-reservation flow control, control flits traverse the network in advance of data flits, reserving buffers ahead of time. Scheduling ahead of data arrival allows buffers to be held only when the buffers are in actual use, unlike other flow control methods. The paper claims that with just 6 buffers, the throughput of flit-reservation flow control (77%) approaches that of virtual-channel flow control using 16 buffers (80%), suggesting a significant buffer savings as a result of efficient buffer utilization. Control flits traverse the network ahead of data flits to reserve buffer space before the data flits arrive. When the data flits do arrive, they are buffered according to the precalculated reservation. The advanced scheduling enabled by flit reservation allows buffers to be used immediately after departure of the flit, as opposed to other flow control methods where buffers cannot be freed until downstream status information (i.e. credits) are sent back, resulting in a round-trip latency where the buffer cannot be used for other data. One of the benefits pointed out about flit reservation flow control is that for a fixed amount of buffer space, saturation throughput is increased because of more efficient buffer scheduling. The paper claims that for an 8x8 mesh network with eight flit buffers per input, virtual-channel flow control 1 saturates at 63% of the bisection bandwidth while flit-reservation flow control achieves a performance of 77% of bandwidth, resulting in a 20% improvement with equal buffer storage. A clear strength of flit-reservation flow control is apparent in the comparison made between buffer utilization of wormhole and virtual-channel flow control and flit-reservation flow control. In the first 2 allocation schemes, buffers are used according to the following figure: Buffer Turnaround Time of Wormhole and Virtual-Channel Flow Control The buffer is first allocated and held from the time the data flit departs the current node, to when it is processed by the next node, to the time the flow control signal returns to inform the current node that the buffer can be released. Only after this turnaround can the buffer be reused. So the turnaround time of the buffer is at least the sum of the propagation delay of the data flit in the forward direction and the flow control back. In flit-reservation flow control, this turnaround time is essentially zero. Another benefit of flit-reservation flow control is described as providing similar advantages of statically-scheduled flow control, where the flow of data is 'compiled' before runtime. Flit-reservation flow control provides an added benefit in that it supports the flexibility of a dynamically routed network. Instead of scheduling resources at compile time, the scheduling decisions are made when data packets are injected, allowing the schedule to adapt to different traffic patterns. Both methods use buffers efficiently, with immediate turnaround and routing and arbitration latency hidden, but flit-reservation flow control doesn't sacrifice flexibility. A drawback of flit-reservation flow control stems from its usage of a shared pool of buffers. If the buffer pool is small relative to the length of the packets and a packet is blocked, all it's data flits are stalled and hold buffers. The situation becomes worse with an increasing length in packets. So when the buffer pool size is small relative to the packet length, active packets cannot bypass blocked packets. A thorough description of the architecture and experimental results are well documented in this paper. This type of buffer allocation can be used in other types of datapath architectures. It is similar to scoreboarding, where the control packets serve as scorecards that are passed along the different nodes to allocate resources. The paper did fail to fully describe the amount of changes needed to implement error recovery. If there is a severe penalty in resources to provide data integrity, that could offset the resource savings in going with this buffer allocation scheme. With the way designs are scaling nowadays, data integrity and error recovery is becoming more important. Virtual Channels Planning for Networks-on-chip 3 The basic idea of this paper is that, due to the limited buffer space, it should be used efficiently. As a result, some physical links should use more virtual channels, and some less, just like the following graph for a mesh network. The paper used an algorithm: First, let the network construct without virtual channel, and find out the port with most contention, add a virtual channel to it and then run the simulation again This VC allocation process could decrease the need for buffer space a lot, as the follow table shows: Critique of the Topic Write a critique of the topic: Is the problem the right one? Is there a way to recast the problem to accomplish the same end in an easier way? Do the solutions address the critical issues associated with this topic? Are there any key issues that have not been addressed? How would you address the problem? Would you use one of these solutions or would you take a different approach? --Zhengli 05:22, 3 May 2007 (UTC)For virtual channel Planning for Networks-on-Chip, the idea is very interesting, but seems the evaluation of contention is not in a good way, and it overestimate the complexity to build a cutomized router. --Polkeem 05:41, 3 May 2007 (UTC) For this Critique section, I think it is saying we need to critique the topic we've chosen, and not really critique the papers we've read so much. Even though we are supposed to show how the papers address the problem we've stated, I think we're supposed to use these papers as tools to discuss the problem more and solutions to the problems. Actual critique of the paper seems like it should go into the corresponding 'Solutions' sections. What do you guys think? Confusion (Delete Me) A virtual channel consists of a buffer that can hold one or more flits of a packet and associated state information. Several virtual channels may share the bandwidth of a single physical channel.1 When we mention "virtual channel", it means a kind of flow control method in interconnection networks, not a term in telecommnuication. See the Confused definition References http://cag.csail.mit.edu/PSRG/papers/dally-ieee92.pdf W. J. Dally, "Virtual Channel Flow Control", March 1992 http://cva.stanford.edu/publications/1999/flit_rsvn.pdf L. Peh, W. J. Dally, "Flit Reservation Flow Control", 1999 http://doi.ieeecomputersociety.org/10.1109/ISQED.2007.169Ting-Chun Huang, Umit Y. Ogras, Radu Marculescu, "Virtual Channels Planning for Networks-on-Chip" 4. Abdel-Halim Smai, Dhabaleswar K. Panda, Lars-Erik Thorelli, "Prioritized Demand Multiplexing (PDM): A Low-Latency Virtual Channel Flow Control Framework for Prioritized Traffic" 5. Jose Duato1, Sudhakar Yalamanchili2, M. Blanca Caminero3, Damon Love2, Francisco J. Quiles3, "MMR: A High-Performance Multimedia Router - Architecture and Design Trade-Offs" 6. Chrysostomos A. Nicopoulos, Dongkook Park, Jongman Kim, N. Vijaykrishnan, Mazin S. Yousif , Chita R. Das ViChaR: "A Dynamic Virtual Channel Regulator for Network-on-Chip Routers" 7. J. Hu, R. Marculescu, "Application-Specific Buffer Space Allocation for Networks-on-Chip Router Design"